package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;

/**
 * @author：zzc
 * @date: 2022/9/1
 */
public class 链表中倒数第k个节点 {

    //输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，
    //本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。
    //例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、
    //5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);
        node1.next.next.next.next.next = new ListNode(6);

        System.out.println(StopWatchTemplate.doSupplier(() -> getLastkNode(node1, 5)));
    }

    private static ListNode getLastkNode(ListNode node1, int k) {
        // 确定链表的长度
        // 遍历链表 输出第 n-K+1 的节点
        if (node1 == null) {
            return null;
        }
        int num = 1;
        ListNode p = node1;
        while (p.next != null) {
            p = p.next;
            num++;
        }

        int i = 1;
        while (node1 != null) {
            if (i == num - k + 1) {
                return node1;
            }
            node1 = node1.next;
            i++;

        }
        return null;

    }


}
